
<!DOCTYPE html>
<html>

	<head>
	<title>CAIJL's Blog</title>
	<meta charset="utf-8"/>
	<link rel="stylesheet" href="/font-awesome-4.7.0/css/font-awesome.min.css">

	<link rel="stylesheet" href="/bootstrap-3.3.7/css/bootstrap.min.css">
	<script src="/jquery-2.1.1/jquery.min.js"></script>
	<script src="/bootstrap-3.3.7/js/bootstrap.min.js"></script>

	<link rel="stylesheet" href="/css/bootstrap-slider.min.css">
	<script src="/js/bootstrap-slider.min.js"></script>
	
	<link rel="stylesheet" href="/css/main.css">
	<script src="/js/main.js"></script>
	
	<link rel="stylesheet" href="/css/cursor.css">
	<script src="/js/cursor.js"></script>
	
	
	<link rel="stylesheet" href="/css/code.css">
	<!--link rel="stylesheet" href="/css/markdown.css"-->
	
	<link rel="stylesheet" href="/css/head.css">

	<script src="/js/window.js"></script>
	<script src='//unpkg.com/valine/dist/Valine.min.js'></script>
	</head>
<body>

	<link rel="stylesheet" href="/katex/katex.min.css" crossorigin="anonymous">
	<script src="/katex/katex.min.js" crossorigin="anonymous"></script>
	<script src="/katex/contrib/mathtex-script-type.min.js" defer></script>
	<script defer src="/katex/contrib/auto-render.min.js"crossorigin="anonymous"
	    onload="renderMathInElement(document.body);"></script>
	<script>document.addEventListener("DOMContentLoaded", function() {renderMathInElement(document.body,{"delimiters":[{left: "$", right: "$", display: false}]});});</script>
	<nav class="navbar navbar-default header card" role="navigation" style="width: 100%;">
	<div class="container-fluid"> 
	<div class="navbar-header">
		<button type="button" class="navbar-toggle" data-toggle="collapse"
				data-target="#example-navbar-collapse">
			<span class="icon-bar"></span>
			<span class="icon-bar"></span>
			<span class="icon-bar"></span>
		</button>
		<a class="navbar-brand" href="/"><span><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="bold">C</mi><mi mathvariant="bold">A</mi><mi mathvariant="bold">I</mi><mi mathvariant="bold">J</mi><msup><mi mathvariant="bold">L</mi><mo mathvariant="bold" lspace="0em" rspace="0em">′</mo></msup><mi mathvariant="bold">s</mi><mi mathvariant="bold">B</mi><mi mathvariant="bold">L</mi><mi mathvariant="bold">O</mi><mi mathvariant="bold">G</mi></mrow><annotation encoding="application/x-tex">\mathbf{CAIJL'sBLOG}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height: 0.751892em; vertical-align: 0em;"></span><span class="mord"><span class="mord mathbf">C</span><span class="mord mathbf">A</span><span class="mord mathbf">I</span><span class="mord mathbf">J</span><span class="mord"><span class="mord mathbf">L</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height: 0.751892em;"><span class="" style="top: -3.063em; margin-right: 0.05em;"><span class="pstrut" style="height: 2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathbf mtight">′</span></span></span></span></span></span></span></span></span><span class="mord mathbf">s</span><span class="mord mathbf">B</span><span class="mord mathbf">L</span><span class="mord mathbf">O</span><span class="mord mathbf">G</span></span></span></span></span></span></a>
	</div>
	<div class="collapse navbar-collapse" id="example-navbar-collapse">
		<ul class="nav navbar-nav" style="background-color:#fcfcfc">
			<li><a href="/"><i class="menu-item-icon fa fa-fw fa-home"></i>首页</a></li>
			<li><a href="/archives/"><i class="menu-item-icon fa fa-fw fa-archive"></i>文章</a></li>
			<li><a href="/tags/"><i class="menu-item-icon fa fa-fw fa-tags"></i>标签</a></li>
			<li><a href="/settings/"><i class="menu-item-icon fa fa-fw fa-cogs"></i>设置</a></li>
			<!--li><a href="/about/"><i class="menu-item-icon fa fa-fw fa-user"></i>关于</a></li-->
			<li><a href="/games/"><i class="menu-item-icon fa fa-fw fa-gamepad"></i>其它</a></li>
			

		</ul>
	</div>
	</div>
	</nav>
<div class="container">
	<div style="height: 60px;"></div>
	<div class="row" >
		<div class="col-md-8">
			<div class="panel panel-default card" style="padding: 10px;position: relative;">
                <img src='/img/bg/46.png' style="width:100%"/>
				<span style="position: absolute;left:15px;bottom:15px;width:90%;"><font class="view-text" style="color:#fcfcfc;font-size:25px">题解 P7470 【[NOI Online 2021 提高组] 岛屿探险】</font><br><a href="/tags/2021/" class="tag"><span  style="background-color: rgb(52, 152, 219);">2021</span></a>&nbsp;<a href="/tags/tire/" class="tag"><span  style="background-color: rgb(231, 76, 60);">tire</span></a>&nbsp;<a href="/tags/分块/" class="tag"><span  style="background-color: rgb(231, 76, 60);">分块</span></a>&nbsp;<a href="/tags/题解/" class="tag"><span  style="background-color: rgb(82, 196, 26);">题解</span></a></span>
			</div>
			<div class="panel panel-default card" style="padding: 10px;" id="main">
                <h2 id="_1">题意</h2>
<p><input value="在洛谷上查看" type="button" onclick="creat('https://www.luogu.com.cn/problem/P7470')" class="btn btn-link"/></p>
<p>有两个长度为 <script type="math/tex">n</script> 的序列 <script type="math/tex">a,b</script>，给出 <script type="math/tex">q</script> 组询问，每组询问有 <script type="math/tex">l,r,c,d</script>，问在 <script type="math/tex">i\in[l,r]</script> 有多少满足 <script type="math/tex">(a_i\oplus c)\le \min(b_i,d)</script>
</p>
<h2 id="_2">题解</h2>
<p>暴力开 <script type="math/tex">\rm O_2</script>
<script type="math/tex">80</script> 分就很离谱。</p>
<p>一个一个点往下看。</p>
<h3 id="1sim-4">
<script type="math/tex">1\sim 4</script>
</h3>
<p>暴力随便跑好吧。</p>
<p>循环展开参见 <code>namespace solve1</code></p>
<h3 id="5sim-7-maxd_ileq-minb_i">
<script type="math/tex">5\sim 7</script>
<script type="math/tex">\max\{d_i\}\leq \min\{b_i\}</script>
</h3>
<p>这个点 <script type="math/tex">(a_i\oplus c)\le \min(b_i,d)</script> 事实上就是 <script type="math/tex">(a_i\oplus c)\le d_i</script>。这个 <script type="math/tex">[l,r]</script> 明显可以差分，变成 <script type="math/tex">[1,r]-[1,l-1]</script>。</p>
<p>于是问题就变成了对于 <script type="math/tex">[1,x]</script> 的个数，那么先对 <script type="math/tex">[1,x]</script> 的 <script type="math/tex">a_i</script> 建一棵字母树，然后给定 <script type="math/tex">c,d</script> 问有多少 <script type="math/tex">a_i</script> 可以满足上式。</p>
<p>分类讨论：</p>
<ol>
<li>
<script type="math/tex">d</script> 这一位为 <script type="math/tex">0</script>，那么只能走 <script type="math/tex">c</script> 这一位取反的值，这一位才能比 <script type="math/tex">d</script> 小；</li>
<li>
<script type="math/tex">d</script> 这一位为 <script type="math/tex">1</script>，若这一位与 <script type="math/tex">c</script> 相同得到 <script type="math/tex">0</script>，往这一路走所有的 <script type="math/tex">a</script> 都满足条件，若不相同则得到 <script type="math/tex">1</script>，继续往下走。</li>
</ol>
<p>那么单次插入复杂度 <script type="math/tex">O(24)</script>，单次查询复杂度 <script type="math/tex">O(24)</script>，总复杂度 <script type="math/tex">O(24n+24q)</script>。</p>
<p>
<script type="math/tex">\rm 01Tire</script> 的实现参见 <code>namespace T1</code>，差分的实现参见 <code>namespace solve2</code></p>
<h3 id="8sim-11-mind_igeq-maxb_i">
<script type="math/tex">8\sim 11</script>
<script type="math/tex">\min\{d_i\}\geq \max\{b_i\}</script>
</h3>
<p>这个也挺容易构造的。。。</p>
<p>由于约束条件只有 <script type="math/tex">b_i</script>，考虑对 <script type="math/tex">a,b</script> 构造出可行的 <script type="math/tex">c</script>，构造方法还是分类讨论：</p>
<ol>
<li>
<script type="math/tex">b</script> 这一位是 <script type="math/tex">0</script>，则 <script type="math/tex">c</script> 这一位只能和 <script type="math/tex">a</script> 相反不然不可能小于等于 <script type="math/tex">b</script>；</li>
<li>
<script type="math/tex">b</script> 这一位是 <script type="math/tex">1</script>，则 <script type="math/tex">c</script> 这一位于 <script type="math/tex">a</script> 相等则必小于，或者不相等就处理下一位。</li>
</ol>
<p>
<script type="math/tex">\rm 01Tire</script> 的实现参见 <code>namespace T2</code>，差分的实现参见 <code>namespace solve3</code></p>
<h3 id="12sim13-l_i1r_in">
<script type="math/tex">12\sim13</script>
<script type="math/tex">l_i=1,r_i=n</script>
</h3>
<p>这个在考场上也写出来了。在这样的情况下，每个 <script type="math/tex">(a_i,b_i)</script> 无序，因此对 <script type="math/tex">b_i</script> 排序完全没有影响。那么把询问 <script type="math/tex">c,d</script> 看做是两部分：<script type="math/tex">b\le d</script> 的和 <script type="math/tex">b>d</script> 的。把 <script type="math/tex">d</script> 排序，用 <code>T1</code> 的方法处理 <script type="math/tex">b\le d</script>。反过来用 <code>T2</code> 处理 <script type="math/tex">b>d</script>。具体实现可以参考 <code>namespace solve4</code></p>
<p>复杂度 <script type="math/tex">O(n\log n+24q)</script>
</p>
<h3 id="14sim20">
<script type="math/tex">14\sim20</script>
</h3>
<p>没有任何限制，可以强行改到 <script type="math/tex">12\sim13</script>。</p>
<p>对序列分块,那么整块就是 <script type="math/tex">12\sim13</script> 的情况，零散块直接暴力即可。为了速度循环展开了一下下。</p>
<p>时间复杂度 <script type="math/tex">O\left(q\log q+\dfrac nT(T\log T+24q)\right)</script>，应该是 <script type="math/tex">T=1800</script> 左右速度过得去。</p>
<p>这份菜得离谱代码不开 <script type="math/tex">\rm O_2</script> 也是稳过的。</p>
<h2 id="_3">代码</h2>
<div class="highlight"><pre><span></span><code><span class="linenos" data-linenos="  1 "></span><span class="cp">#include</span><span class="cpf">&lt;bits/stdc++.h&gt;</span><span class="cp"></span>
<span class="linenos" data-linenos="  2 "></span><span class="cp">#define min(a,b) (a&lt;b?a:b)</span>
<span class="linenos" data-linenos="  3 "></span><span class="cp">#define max(a,b) (a&gt;b?a:b)</span>
<span class="linenos" data-linenos="  4 "></span><span class="k">const</span> <span class="kt">int</span> <span class="n">N</span><span class="o">=</span><span class="mf">1e5</span><span class="o">+</span><span class="mi">10</span><span class="p">;</span>
<span class="linenos" data-linenos="  5 "></span><span class="cp">#define faster</span>
<span class="linenos" data-linenos="  6 "></span><span class="k">namespace</span> <span class="n">in</span><span class="p">{</span>
<span class="linenos" data-linenos="  7 "></span>    <span class="cp">#ifdef faster</span>
<span class="linenos" data-linenos="  8 "></span>    <span class="kt">char</span> <span class="n">buf</span><span class="p">[</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="mi">21</span><span class="p">],</span><span class="o">*</span><span class="n">p1</span><span class="o">=</span><span class="n">buf</span><span class="p">,</span><span class="o">*</span><span class="n">p2</span><span class="o">=</span><span class="n">buf</span><span class="p">;</span>
<span class="linenos" data-linenos="  9 "></span>    <span class="kr">inline</span> <span class="kt">int</span> <span class="n">getc</span><span class="p">(){</span><span class="k">return</span> <span class="n">p1</span><span class="o">==</span><span class="n">p2</span><span class="o">&amp;&amp;</span><span class="p">(</span><span class="n">p2</span><span class="o">=</span><span class="p">(</span><span class="n">p1</span><span class="o">=</span><span class="n">buf</span><span class="p">)</span><span class="o">+</span><span class="n">fread</span><span class="p">(</span><span class="n">buf</span><span class="p">,</span><span class="mi">1</span><span class="p">,</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="mi">21</span><span class="p">,</span><span class="n">stdin</span><span class="p">),</span><span class="n">p1</span><span class="o">==</span><span class="n">p2</span><span class="p">)</span><span class="o">?</span><span class="nl">EOF</span><span class="p">:</span><span class="o">*</span><span class="n">p1</span><span class="o">++</span><span class="p">;}</span>
<span class="linenos" data-linenos=" 10 "></span>    <span class="cp">#else</span>
<span class="linenos" data-linenos=" 11 "></span>    <span class="kr">inline</span> <span class="kt">int</span> <span class="n">getc</span><span class="p">(){</span><span class="k">return</span> <span class="nf">getchar</span><span class="p">();}</span>
<span class="linenos" data-linenos=" 12 "></span>    <span class="cp">#endif</span>
<span class="linenos" data-linenos=" 13 "></span>    <span class="k">template</span> <span class="o">&lt;</span><span class="k">typename</span> <span class="nc">T</span><span class="o">&gt;</span><span class="kr">inline</span> <span class="kt">void</span> <span class="n">read</span><span class="p">(</span><span class="n">T</span><span class="o">&amp;</span> <span class="n">t</span><span class="p">){</span>
<span class="linenos" data-linenos=" 14 "></span>        <span class="n">t</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="kt">int</span> <span class="n">f</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="kt">char</span> <span class="n">ch</span><span class="o">=</span><span class="n">getc</span><span class="p">();</span><span class="k">while</span> <span class="p">(</span><span class="o">!</span><span class="n">isdigit</span><span class="p">(</span><span class="n">ch</span><span class="p">)){</span><span class="k">if</span><span class="p">(</span><span class="n">ch</span><span class="o">==</span><span class="sc">&#39;-&#39;</span><span class="p">)</span><span class="n">f</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span><span class="n">ch</span><span class="o">=</span><span class="n">getc</span><span class="p">();}</span>
<span class="linenos" data-linenos=" 15 "></span>        <span class="k">while</span><span class="p">(</span><span class="n">isdigit</span><span class="p">(</span><span class="n">ch</span><span class="p">)){</span><span class="n">t</span><span class="o">=</span><span class="n">t</span><span class="o">*</span><span class="mi">10</span><span class="o">+</span><span class="n">ch</span><span class="mi">-48</span><span class="p">;</span><span class="n">ch</span> <span class="o">=</span> <span class="n">getc</span><span class="p">();}</span><span class="k">if</span><span class="p">(</span><span class="n">f</span><span class="p">)</span><span class="n">t</span><span class="o">=-</span><span class="n">t</span><span class="p">;</span>
<span class="linenos" data-linenos=" 16 "></span>    <span class="p">}</span>
<span class="linenos" data-linenos=" 17 "></span>    <span class="k">template</span> <span class="o">&lt;</span><span class="k">typename</span> <span class="nc">T</span><span class="p">,</span><span class="k">typename</span><span class="p">...</span> <span class="n">Args</span><span class="o">&gt;</span> <span class="kr">inline</span> <span class="kt">void</span> <span class="n">read</span><span class="p">(</span><span class="n">T</span><span class="o">&amp;</span> <span class="n">t</span><span class="p">,</span> <span class="n">Args</span><span class="o">&amp;</span><span class="p">...</span> <span class="n">args</span><span class="p">){</span><span class="n">read</span><span class="p">(</span><span class="n">t</span><span class="p">);</span><span class="n">read</span><span class="p">(</span><span class="n">args</span><span class="p">...);}</span>
<span class="linenos" data-linenos=" 18 "></span><span class="p">}</span>
<span class="linenos" data-linenos=" 19 "></span><span class="k">namespace</span> <span class="n">out</span><span class="p">{</span>
<span class="linenos" data-linenos=" 20 "></span>    <span class="kt">char</span> <span class="n">buffer</span><span class="p">[</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="mi">21</span><span class="p">];</span><span class="kt">int</span> <span class="n">p1</span><span class="o">=</span><span class="mi">-1</span><span class="p">;</span><span class="k">const</span> <span class="kt">int</span> <span class="n">p2</span> <span class="o">=</span> <span class="p">(</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="mi">21</span><span class="p">)</span><span class="mi">-1</span><span class="p">;</span>
<span class="linenos" data-linenos=" 21 "></span>    <span class="kr">inline</span> <span class="kt">void</span> <span class="n">flush</span><span class="p">(){</span><span class="n">fwrite</span><span class="p">(</span><span class="n">buffer</span><span class="p">,</span><span class="mi">1</span><span class="p">,</span><span class="n">p1</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span><span class="n">stdout</span><span class="p">),</span><span class="n">p1</span><span class="o">=</span><span class="mi">-1</span><span class="p">;}</span>
<span class="linenos" data-linenos=" 22 "></span>    <span class="kr">inline</span> <span class="kt">void</span> <span class="n">putc</span><span class="p">(</span><span class="k">const</span> <span class="kt">char</span> <span class="o">&amp;</span><span class="n">x</span><span class="p">)</span> <span class="p">{</span><span class="k">if</span><span class="p">(</span><span class="n">p1</span><span class="o">==</span><span class="n">p2</span><span class="p">)</span><span class="n">flush</span><span class="p">();</span><span class="n">buffer</span><span class="p">[</span><span class="o">++</span><span class="n">p1</span><span class="p">]</span><span class="o">=</span><span class="n">x</span><span class="p">;}</span>
<span class="linenos" data-linenos=" 23 "></span>    <span class="k">template</span> <span class="o">&lt;</span><span class="k">typename</span> <span class="nc">T</span><span class="o">&gt;</span><span class="kt">void</span> <span class="n">write</span><span class="p">(</span><span class="n">T</span> <span class="n">x</span><span class="p">)</span> <span class="p">{</span>
<span class="linenos" data-linenos=" 24 "></span>        <span class="k">static</span> <span class="kt">char</span> <span class="n">buf</span><span class="p">[</span><span class="mi">15</span><span class="p">];</span><span class="k">static</span> <span class="kt">int</span> <span class="n">len</span><span class="o">=</span><span class="mi">-1</span><span class="p">;</span><span class="k">if</span><span class="p">(</span><span class="n">x</span><span class="o">&gt;=</span><span class="mi">0</span><span class="p">){</span><span class="k">do</span><span class="p">{</span><span class="n">buf</span><span class="p">[</span><span class="o">++</span><span class="n">len</span><span class="p">]</span><span class="o">=</span><span class="n">x</span><span class="o">%</span><span class="mi">10</span><span class="o">+</span><span class="mi">48</span><span class="p">,</span><span class="n">x</span><span class="o">/=</span><span class="mi">10</span><span class="p">;}</span><span class="k">while</span> <span class="p">(</span><span class="n">x</span><span class="p">);}</span><span class="k">else</span><span class="p">{</span><span class="n">putc</span><span class="p">(</span><span class="sc">&#39;-&#39;</span><span class="p">);</span><span class="k">do</span> <span class="p">{</span><span class="n">buf</span><span class="p">[</span><span class="o">++</span><span class="n">len</span><span class="p">]</span><span class="o">=-</span><span class="p">(</span><span class="n">x</span><span class="o">%</span><span class="mi">10</span><span class="p">)</span><span class="o">+</span><span class="mi">48</span><span class="p">,</span><span class="n">x</span><span class="o">/=</span><span class="mi">10</span><span class="p">;}</span><span class="k">while</span><span class="p">(</span><span class="n">x</span><span class="p">);}</span>
<span class="linenos" data-linenos=" 25 "></span>        <span class="k">while</span> <span class="p">(</span><span class="n">len</span><span class="o">&gt;=</span><span class="mi">0</span><span class="p">)</span><span class="n">putc</span><span class="p">(</span><span class="n">buf</span><span class="p">[</span><span class="n">len</span><span class="p">]),</span><span class="o">--</span><span class="n">len</span><span class="p">;</span>
<span class="linenos" data-linenos=" 26 "></span>    <span class="p">}</span>
<span class="linenos" data-linenos=" 27 "></span><span class="p">}</span>
<span class="linenos" data-linenos=" 28 "></span><span class="kt">int</span> <span class="n">n</span><span class="p">,</span><span class="n">q</span><span class="p">,</span><span class="n">a</span><span class="p">[</span><span class="n">N</span><span class="p">],</span><span class="n">b</span><span class="p">[</span><span class="n">N</span><span class="p">],</span><span class="n">l</span><span class="p">[</span><span class="n">N</span><span class="p">],</span><span class="n">r</span><span class="p">[</span><span class="n">N</span><span class="p">],</span><span class="n">c</span><span class="p">[</span><span class="n">N</span><span class="p">],</span><span class="n">d</span><span class="p">[</span><span class="n">N</span><span class="p">],</span><span class="n">ans</span><span class="p">[</span><span class="n">N</span><span class="p">];</span>
<span class="linenos" data-linenos=" 29 "></span><span class="k">namespace</span> <span class="n">solve1</span><span class="p">{</span>
<span class="linenos" data-linenos=" 30 "></span>    <span class="c1">//暴力+循环展开</span>
<span class="linenos" data-linenos=" 31 "></span>    <span class="kt">void</span> <span class="nf">work</span><span class="p">(){</span>
<span class="linenos" data-linenos=" 32 "></span>        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">kk</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">kk</span><span class="o">&lt;=</span><span class="n">q</span><span class="p">;</span><span class="n">kk</span><span class="o">++</span><span class="p">){</span>
<span class="linenos" data-linenos=" 33 "></span>            <span class="k">register</span> <span class="kt">int</span> <span class="n">ans1</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span><span class="n">ans2</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span><span class="n">ans3</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span><span class="n">ans4</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span><span class="n">ans5</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span><span class="n">ans6</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span><span class="n">ans7</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span><span class="n">ans8</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
<span class="linenos" data-linenos=" 34 "></span>            <span class="k">register</span> <span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="n">l</span><span class="p">[</span><span class="n">kk</span><span class="p">],</span><span class="n">R</span><span class="o">=</span><span class="n">r</span><span class="p">[</span><span class="n">kk</span><span class="p">],</span><span class="n">C</span><span class="o">=</span><span class="n">c</span><span class="p">[</span><span class="n">kk</span><span class="p">],</span><span class="n">D</span><span class="o">=</span><span class="n">d</span><span class="p">[</span><span class="n">kk</span><span class="p">];</span>
<span class="linenos" data-linenos=" 35 "></span>            <span class="k">for</span><span class="p">(;</span><span class="n">i</span><span class="o">+</span><span class="mi">7</span><span class="o">&lt;=</span><span class="n">R</span><span class="p">;</span><span class="n">i</span><span class="o">+=</span><span class="mi">8</span><span class="p">)</span>
<span class="linenos" data-linenos=" 36 "></span>                <span class="n">ans1</span><span class="o">+=</span><span class="p">((</span><span class="n">a</span><span class="p">[</span><span class="n">i</span>  <span class="p">]</span><span class="o">^</span><span class="n">C</span><span class="p">)</span><span class="o">&lt;=</span><span class="n">min</span><span class="p">(</span><span class="n">b</span><span class="p">[</span><span class="n">i</span>  <span class="p">],</span><span class="n">D</span><span class="p">)),</span>
<span class="linenos" data-linenos=" 37 "></span>                <span class="n">ans2</span><span class="o">+=</span><span class="p">((</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span><span class="o">^</span><span class="n">C</span><span class="p">)</span><span class="o">&lt;=</span><span class="n">min</span><span class="p">(</span><span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">],</span><span class="n">D</span><span class="p">)),</span>
<span class="linenos" data-linenos=" 38 "></span>                <span class="n">ans3</span><span class="o">+=</span><span class="p">((</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="mi">2</span><span class="p">]</span><span class="o">^</span><span class="n">C</span><span class="p">)</span><span class="o">&lt;=</span><span class="n">min</span><span class="p">(</span><span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="mi">2</span><span class="p">],</span><span class="n">D</span><span class="p">)),</span>
<span class="linenos" data-linenos=" 39 "></span>                <span class="n">ans4</span><span class="o">+=</span><span class="p">((</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="mi">3</span><span class="p">]</span><span class="o">^</span><span class="n">C</span><span class="p">)</span><span class="o">&lt;=</span><span class="n">min</span><span class="p">(</span><span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="mi">3</span><span class="p">],</span><span class="n">D</span><span class="p">)),</span>
<span class="linenos" data-linenos=" 40 "></span>                <span class="n">ans5</span><span class="o">+=</span><span class="p">((</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="mi">4</span><span class="p">]</span><span class="o">^</span><span class="n">C</span><span class="p">)</span><span class="o">&lt;=</span><span class="n">min</span><span class="p">(</span><span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="mi">4</span><span class="p">],</span><span class="n">D</span><span class="p">)),</span>
<span class="linenos" data-linenos=" 41 "></span>                <span class="n">ans6</span><span class="o">+=</span><span class="p">((</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="mi">5</span><span class="p">]</span><span class="o">^</span><span class="n">C</span><span class="p">)</span><span class="o">&lt;=</span><span class="n">min</span><span class="p">(</span><span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="mi">5</span><span class="p">],</span><span class="n">D</span><span class="p">)),</span>
<span class="linenos" data-linenos=" 42 "></span>                <span class="n">ans7</span><span class="o">+=</span><span class="p">((</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="mi">6</span><span class="p">]</span><span class="o">^</span><span class="n">C</span><span class="p">)</span><span class="o">&lt;=</span><span class="n">min</span><span class="p">(</span><span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="mi">6</span><span class="p">],</span><span class="n">D</span><span class="p">)),</span>
<span class="linenos" data-linenos=" 43 "></span>                <span class="n">ans8</span><span class="o">+=</span><span class="p">((</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="mi">7</span><span class="p">]</span><span class="o">^</span><span class="n">C</span><span class="p">)</span><span class="o">&lt;=</span><span class="n">min</span><span class="p">(</span><span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="mi">7</span><span class="p">],</span><span class="n">D</span><span class="p">));</span>
<span class="linenos" data-linenos=" 44 "></span>            <span class="k">for</span><span class="p">(;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">R</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span>
<span class="linenos" data-linenos=" 45 "></span>                <span class="n">ans1</span><span class="o">+=</span><span class="p">((</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">^</span><span class="n">C</span><span class="p">)</span><span class="o">&lt;=</span><span class="n">min</span><span class="p">(</span><span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">],</span><span class="n">D</span><span class="p">));</span>  
<span class="linenos" data-linenos=" 46 "></span>            <span class="n">ans</span><span class="p">[</span><span class="n">kk</span><span class="p">]</span><span class="o">=</span><span class="n">ans1</span><span class="o">+</span><span class="n">ans2</span><span class="o">+</span><span class="n">ans3</span><span class="o">+</span><span class="n">ans4</span><span class="o">+</span><span class="n">ans5</span><span class="o">+</span><span class="n">ans6</span><span class="o">+</span><span class="n">ans7</span><span class="o">+</span><span class="n">ans8</span><span class="p">;</span>
<span class="linenos" data-linenos=" 47 "></span>        <span class="p">}</span>
<span class="linenos" data-linenos=" 48 "></span>    <span class="p">}</span>
<span class="linenos" data-linenos=" 49 "></span><span class="p">}</span>
<span class="linenos" data-linenos=" 50 "></span>
<span class="linenos" data-linenos=" 51 "></span><span class="k">const</span> <span class="kt">int</span> <span class="n">L</span><span class="o">=</span><span class="mi">24</span><span class="p">;</span>
<span class="linenos" data-linenos=" 52 "></span><span class="kt">void</span> <span class="nf">pre</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span><span class="kt">int</span> <span class="o">*</span><span class="n">tmp</span><span class="p">){</span><span class="kt">int</span> <span class="n">now</span><span class="o">=</span><span class="n">L</span><span class="mi">-1</span><span class="p">;</span><span class="k">while</span><span class="p">(</span><span class="n">now</span><span class="o">&gt;=</span><span class="mi">0</span><span class="p">)</span><span class="n">tmp</span><span class="p">[</span><span class="n">now</span><span class="p">]</span><span class="o">=</span><span class="n">x</span><span class="o">&amp;</span><span class="mi">1</span><span class="p">,</span><span class="n">x</span><span class="o">&gt;&gt;=</span><span class="mi">1</span><span class="p">,</span><span class="n">now</span><span class="o">--</span><span class="p">;}</span>
<span class="linenos" data-linenos=" 53 "></span><span class="k">namespace</span> <span class="n">T1</span><span class="p">{</span>
<span class="linenos" data-linenos=" 54 "></span>    <span class="kt">int</span> <span class="n">ch</span><span class="p">[</span><span class="n">N</span><span class="o">*</span><span class="mi">24</span><span class="p">][</span><span class="mi">2</span><span class="p">],</span><span class="n">sz</span><span class="p">[</span><span class="n">N</span><span class="o">*</span><span class="mi">24</span><span class="p">];</span><span class="kt">int</span> <span class="n">tot</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
<span class="linenos" data-linenos=" 55 "></span>    <span class="kt">int</span> <span class="nf">newnode</span><span class="p">(){</span><span class="o">++</span><span class="n">tot</span><span class="p">;</span><span class="n">ch</span><span class="p">[</span><span class="n">tot</span><span class="p">][</span><span class="mi">0</span><span class="p">]</span><span class="o">=</span><span class="n">ch</span><span class="p">[</span><span class="n">tot</span><span class="p">][</span><span class="mi">1</span><span class="p">]</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">sz</span><span class="p">[</span><span class="n">tot</span><span class="p">]</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="k">return</span> <span class="n">tot</span><span class="p">;}</span>
<span class="linenos" data-linenos=" 56 "></span>    <span class="kt">void</span> <span class="nf">insert</span><span class="p">(</span><span class="kt">int</span><span class="o">*</span><span class="n">tmp</span><span class="p">){</span>
<span class="linenos" data-linenos=" 57 "></span>        <span class="kt">int</span> <span class="n">now</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
<span class="linenos" data-linenos=" 58 "></span>        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">L</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
<span class="linenos" data-linenos=" 59 "></span>            <span class="k">if</span><span class="p">(</span><span class="n">ch</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="n">tmp</span><span class="p">[</span><span class="n">i</span><span class="p">]]</span><span class="o">==</span><span class="mi">0</span><span class="p">)</span><span class="n">ch</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="n">tmp</span><span class="p">[</span><span class="n">i</span><span class="p">]]</span><span class="o">=</span><span class="n">newnode</span><span class="p">();</span>
<span class="linenos" data-linenos=" 60 "></span>            <span class="n">now</span><span class="o">=</span><span class="n">ch</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="n">tmp</span><span class="p">[</span><span class="n">i</span><span class="p">]];</span><span class="n">sz</span><span class="p">[</span><span class="n">now</span><span class="p">]</span><span class="o">++</span><span class="p">;</span>
<span class="linenos" data-linenos=" 61 "></span>        <span class="p">}</span>
<span class="linenos" data-linenos=" 62 "></span>    <span class="p">}</span>
<span class="linenos" data-linenos=" 63 "></span>    <span class="kt">int</span> <span class="nf">qry</span><span class="p">(</span><span class="kt">int</span><span class="o">*</span><span class="n">C</span><span class="p">,</span><span class="kt">int</span><span class="o">*</span><span class="n">D</span><span class="p">){</span>
<span class="linenos" data-linenos=" 64 "></span>        <span class="c1">//求有多少 a^C&lt;=D</span>
<span class="linenos" data-linenos=" 65 "></span>        <span class="kt">int</span> <span class="n">now</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="kt">int</span> <span class="n">ans</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
<span class="linenos" data-linenos=" 66 "></span>        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">L</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
<span class="linenos" data-linenos=" 67 "></span>            <span class="k">if</span><span class="p">(</span><span class="n">C</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">==</span><span class="mi">0</span><span class="o">&amp;&amp;</span><span class="n">D</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">==</span><span class="mi">0</span><span class="p">){</span>
<span class="linenos" data-linenos=" 68 "></span>                <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">ch</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="mi">0</span><span class="p">])</span><span class="k">return</span> <span class="n">ans</span><span class="p">;</span>
<span class="linenos" data-linenos=" 69 "></span>                <span class="n">now</span><span class="o">=</span><span class="n">ch</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="mi">0</span><span class="p">];</span>
<span class="linenos" data-linenos=" 70 "></span>            <span class="p">}</span>
<span class="linenos" data-linenos=" 71 "></span>            <span class="k">if</span><span class="p">(</span><span class="n">C</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">==</span><span class="mi">1</span><span class="o">&amp;&amp;</span><span class="n">D</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">==</span><span class="mi">0</span><span class="p">){</span>
<span class="linenos" data-linenos=" 72 "></span>                <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">ch</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="mi">1</span><span class="p">])</span><span class="k">return</span> <span class="n">ans</span><span class="p">;</span>
<span class="linenos" data-linenos=" 73 "></span>                <span class="n">now</span><span class="o">=</span><span class="n">ch</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="mi">1</span><span class="p">];</span>
<span class="linenos" data-linenos=" 74 "></span>            <span class="p">}</span>
<span class="linenos" data-linenos=" 75 "></span>            <span class="k">if</span><span class="p">(</span><span class="n">C</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">==</span><span class="mi">0</span><span class="o">&amp;&amp;</span><span class="n">D</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">==</span><span class="mi">1</span><span class="p">){</span>
<span class="linenos" data-linenos=" 76 "></span>                <span class="n">ans</span><span class="o">+=</span><span class="n">sz</span><span class="p">[</span><span class="n">ch</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="mi">0</span><span class="p">]];</span>
<span class="linenos" data-linenos=" 77 "></span>                <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">ch</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="mi">1</span><span class="p">])</span><span class="k">return</span> <span class="n">ans</span><span class="p">;</span>
<span class="linenos" data-linenos=" 78 "></span>                <span class="n">now</span><span class="o">=</span><span class="n">ch</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="mi">1</span><span class="p">];</span>
<span class="linenos" data-linenos=" 79 "></span>            <span class="p">}</span>
<span class="linenos" data-linenos=" 80 "></span>            <span class="k">if</span><span class="p">(</span><span class="n">C</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">==</span><span class="mi">1</span><span class="o">&amp;&amp;</span><span class="n">D</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">==</span><span class="mi">1</span><span class="p">){</span>
<span class="linenos" data-linenos=" 81 "></span>                <span class="n">ans</span><span class="o">+=</span><span class="n">sz</span><span class="p">[</span><span class="n">ch</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="mi">1</span><span class="p">]];</span>
<span class="linenos" data-linenos=" 82 "></span>                <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">ch</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="mi">0</span><span class="p">])</span><span class="k">return</span> <span class="n">ans</span><span class="p">;</span>
<span class="linenos" data-linenos=" 83 "></span>                <span class="n">now</span><span class="o">=</span><span class="n">ch</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="mi">0</span><span class="p">];</span>
<span class="linenos" data-linenos=" 84 "></span>            <span class="p">}</span>
<span class="linenos" data-linenos=" 85 "></span>        <span class="p">}</span> 
<span class="linenos" data-linenos=" 86 "></span>        <span class="n">ans</span><span class="o">+=</span><span class="n">sz</span><span class="p">[</span><span class="n">now</span><span class="p">];</span>
<span class="linenos" data-linenos=" 87 "></span>        <span class="k">return</span> <span class="n">ans</span><span class="p">;</span>
<span class="linenos" data-linenos=" 88 "></span>    <span class="p">}</span>
<span class="linenos" data-linenos=" 89 "></span>    <span class="kt">void</span> <span class="nf">clear</span><span class="p">(){</span><span class="n">tot</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">ch</span><span class="p">[</span><span class="mi">0</span><span class="p">][</span><span class="mi">0</span><span class="p">]</span><span class="o">=</span><span class="n">ch</span><span class="p">[</span><span class="mi">0</span><span class="p">][</span><span class="mi">1</span><span class="p">]</span><span class="o">=</span><span class="n">sz</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">=</span><span class="mi">0</span><span class="p">;}</span>
<span class="linenos" data-linenos=" 90 "></span><span class="p">}</span>
<span class="linenos" data-linenos=" 91 "></span><span class="k">namespace</span> <span class="n">T2</span><span class="p">{</span>
<span class="linenos" data-linenos=" 92 "></span>    <span class="kt">int</span> <span class="n">ch</span><span class="p">[</span><span class="n">N</span><span class="o">*</span><span class="mi">24</span><span class="p">][</span><span class="mi">2</span><span class="p">],</span><span class="n">sz</span><span class="p">[</span><span class="n">N</span><span class="o">*</span><span class="mi">24</span><span class="p">];</span><span class="kt">int</span> <span class="n">tot</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
<span class="linenos" data-linenos=" 93 "></span>    <span class="kt">int</span> <span class="nf">newnode</span><span class="p">(){</span><span class="o">++</span><span class="n">tot</span><span class="p">;</span><span class="n">ch</span><span class="p">[</span><span class="n">tot</span><span class="p">][</span><span class="mi">0</span><span class="p">]</span><span class="o">=</span><span class="n">ch</span><span class="p">[</span><span class="n">tot</span><span class="p">][</span><span class="mi">1</span><span class="p">]</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">sz</span><span class="p">[</span><span class="n">tot</span><span class="p">]</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="k">return</span> <span class="n">tot</span><span class="p">;}</span>
<span class="linenos" data-linenos=" 94 "></span>    <span class="kt">void</span> <span class="nf">insert</span><span class="p">(</span><span class="kt">int</span><span class="o">*</span><span class="n">A</span><span class="p">,</span><span class="kt">int</span><span class="o">*</span><span class="n">B</span><span class="p">){</span>
<span class="linenos" data-linenos=" 95 "></span>        <span class="c1">//构造出一棵C要满足的条件的树 </span>
<span class="linenos" data-linenos=" 96 "></span>        <span class="kt">int</span> <span class="n">now</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
<span class="linenos" data-linenos=" 97 "></span>        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">L</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
<span class="linenos" data-linenos=" 98 "></span>            <span class="k">if</span><span class="p">(</span><span class="n">A</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">==</span><span class="mi">0</span><span class="o">&amp;&amp;</span><span class="n">B</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">==</span><span class="mi">0</span><span class="p">){</span>
<span class="linenos" data-linenos=" 99 "></span>                <span class="c1">//此时 C[i] 只能为 0</span>
<span class="linenos" data-linenos="100 "></span>                <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">ch</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="mi">0</span><span class="p">])</span><span class="n">ch</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="mi">0</span><span class="p">]</span><span class="o">=</span><span class="n">newnode</span><span class="p">();</span>
<span class="linenos" data-linenos="101 "></span>                <span class="n">now</span><span class="o">=</span><span class="n">ch</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="mi">0</span><span class="p">];</span>
<span class="linenos" data-linenos="102 "></span>            <span class="p">}</span> 
<span class="linenos" data-linenos="103 "></span>            <span class="k">if</span><span class="p">(</span><span class="n">A</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">==</span><span class="mi">1</span><span class="o">&amp;&amp;</span><span class="n">B</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">==</span><span class="mi">0</span><span class="p">){</span>
<span class="linenos" data-linenos="104 "></span>                <span class="c1">//此时 C[i] 只能为 1</span>
<span class="linenos" data-linenos="105 "></span>                <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">ch</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="mi">1</span><span class="p">])</span><span class="n">ch</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="mi">1</span><span class="p">]</span><span class="o">=</span><span class="n">newnode</span><span class="p">();</span>
<span class="linenos" data-linenos="106 "></span>                <span class="n">now</span><span class="o">=</span><span class="n">ch</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="mi">1</span><span class="p">];</span> 
<span class="linenos" data-linenos="107 "></span>            <span class="p">}</span>
<span class="linenos" data-linenos="108 "></span>            <span class="k">if</span><span class="p">(</span><span class="n">A</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">==</span><span class="mi">0</span><span class="o">&amp;&amp;</span><span class="n">B</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">==</span><span class="mi">1</span><span class="p">){</span>
<span class="linenos" data-linenos="109 "></span>                <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">ch</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="mi">0</span><span class="p">])</span><span class="n">ch</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="mi">0</span><span class="p">]</span><span class="o">=</span><span class="n">newnode</span><span class="p">();</span>
<span class="linenos" data-linenos="110 "></span>                <span class="n">sz</span><span class="p">[</span><span class="n">ch</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="mi">0</span><span class="p">]]</span><span class="o">++</span><span class="p">;</span>
<span class="linenos" data-linenos="111 "></span>                <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">ch</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="mi">1</span><span class="p">])</span><span class="n">ch</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="mi">1</span><span class="p">]</span><span class="o">=</span><span class="n">newnode</span><span class="p">();</span>
<span class="linenos" data-linenos="112 "></span>                <span class="n">now</span><span class="o">=</span><span class="n">ch</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="mi">1</span><span class="p">];</span>
<span class="linenos" data-linenos="113 "></span>            <span class="p">}</span>
<span class="linenos" data-linenos="114 "></span>            <span class="k">if</span><span class="p">(</span><span class="n">A</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">==</span><span class="mi">1</span><span class="o">&amp;&amp;</span><span class="n">B</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">==</span><span class="mi">1</span><span class="p">){</span>
<span class="linenos" data-linenos="115 "></span>                <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">ch</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="mi">1</span><span class="p">])</span><span class="n">ch</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="mi">1</span><span class="p">]</span><span class="o">=</span><span class="n">newnode</span><span class="p">();</span>
<span class="linenos" data-linenos="116 "></span>                <span class="n">sz</span><span class="p">[</span><span class="n">ch</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="mi">1</span><span class="p">]]</span><span class="o">++</span><span class="p">;</span>
<span class="linenos" data-linenos="117 "></span>                <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">ch</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="mi">0</span><span class="p">])</span><span class="n">ch</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="mi">0</span><span class="p">]</span><span class="o">=</span><span class="n">newnode</span><span class="p">();</span>
<span class="linenos" data-linenos="118 "></span>                <span class="n">now</span><span class="o">=</span><span class="n">ch</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="mi">0</span><span class="p">];</span>
<span class="linenos" data-linenos="119 "></span>            <span class="p">}</span>
<span class="linenos" data-linenos="120 "></span>        <span class="p">}</span>
<span class="linenos" data-linenos="121 "></span>        <span class="n">sz</span><span class="p">[</span><span class="n">now</span><span class="p">]</span><span class="o">++</span><span class="p">;</span>
<span class="linenos" data-linenos="122 "></span>    <span class="p">}</span>
<span class="linenos" data-linenos="123 "></span>    <span class="kt">int</span> <span class="nf">qry</span><span class="p">(</span><span class="kt">int</span><span class="o">*</span><span class="n">C</span><span class="p">){</span>
<span class="linenos" data-linenos="124 "></span>        <span class="kt">int</span> <span class="n">now</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span><span class="n">ans</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
<span class="linenos" data-linenos="125 "></span>        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">L</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
<span class="linenos" data-linenos="126 "></span>            <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">ch</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="n">C</span><span class="p">[</span><span class="n">i</span><span class="p">]])</span><span class="k">return</span> <span class="n">ans</span><span class="p">;</span>
<span class="linenos" data-linenos="127 "></span>            <span class="n">now</span><span class="o">=</span><span class="n">ch</span><span class="p">[</span><span class="n">now</span><span class="p">][</span><span class="n">C</span><span class="p">[</span><span class="n">i</span><span class="p">]];</span><span class="n">ans</span><span class="o">+=</span><span class="n">sz</span><span class="p">[</span><span class="n">now</span><span class="p">];</span>
<span class="linenos" data-linenos="128 "></span>        <span class="p">}</span><span class="k">return</span> <span class="n">ans</span><span class="p">;</span>
<span class="linenos" data-linenos="129 "></span>    <span class="p">}</span>
<span class="linenos" data-linenos="130 "></span>    <span class="kt">void</span> <span class="nf">clear</span><span class="p">(){</span><span class="n">tot</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">ch</span><span class="p">[</span><span class="mi">0</span><span class="p">][</span><span class="mi">0</span><span class="p">]</span><span class="o">=</span><span class="n">ch</span><span class="p">[</span><span class="mi">0</span><span class="p">][</span><span class="mi">1</span><span class="p">]</span><span class="o">=</span><span class="n">sz</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">=</span><span class="mi">0</span><span class="p">;}</span>
<span class="linenos" data-linenos="131 "></span><span class="p">}</span>
<span class="linenos" data-linenos="132 "></span><span class="k">namespace</span> <span class="n">solve2</span><span class="p">{</span>
<span class="linenos" data-linenos="133 "></span>    <span class="c1">//max d&lt;=min b 的情况，限制的因素是d </span>
<span class="linenos" data-linenos="134 "></span>    <span class="c1">//首先差分，然后建01-tire</span>
<span class="linenos" data-linenos="135 "></span>    <span class="k">struct</span> <span class="nc">node</span><span class="p">{</span><span class="kt">int</span> <span class="n">c</span><span class="p">,</span><span class="n">d</span><span class="p">,</span><span class="n">op</span><span class="p">,</span><span class="n">id</span><span class="p">;</span><span class="n">node</span><span class="p">(</span><span class="kt">int</span> <span class="n">_</span><span class="p">,</span><span class="kt">int</span> <span class="n">__</span><span class="p">,</span><span class="kt">int</span> <span class="n">___</span><span class="p">,</span><span class="kt">int</span> <span class="n">____</span><span class="p">)</span><span class="o">:</span><span class="n">c</span><span class="p">(</span><span class="n">_</span><span class="p">),</span><span class="n">d</span><span class="p">(</span><span class="n">__</span><span class="p">),</span><span class="n">op</span><span class="p">(</span><span class="n">___</span><span class="p">),</span><span class="n">id</span><span class="p">(</span><span class="n">____</span><span class="p">){}};</span>
<span class="linenos" data-linenos="136 "></span>    <span class="n">std</span><span class="o">::</span><span class="n">vector</span><span class="o">&lt;</span><span class="n">node</span><span class="o">&gt;</span><span class="n">Q</span><span class="p">[</span><span class="n">N</span><span class="p">];</span>
<span class="linenos" data-linenos="137 "></span>    <span class="kt">void</span> <span class="nf">work</span><span class="p">(){</span>
<span class="linenos" data-linenos="138 "></span>        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">q</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span>
<span class="linenos" data-linenos="139 "></span>            <span class="n">Q</span><span class="p">[</span><span class="n">l</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="mi">-1</span><span class="p">].</span><span class="n">push_back</span><span class="p">(</span><span class="n">node</span><span class="p">(</span><span class="n">c</span><span class="p">[</span><span class="n">i</span><span class="p">],</span><span class="n">d</span><span class="p">[</span><span class="n">i</span><span class="p">],</span><span class="mi">-1</span><span class="p">,</span><span class="n">i</span><span class="p">)),</span>
<span class="linenos" data-linenos="140 "></span>            <span class="n">Q</span><span class="p">[</span><span class="n">r</span><span class="p">[</span><span class="n">i</span><span class="p">]].</span><span class="n">push_back</span><span class="p">(</span><span class="n">node</span><span class="p">(</span><span class="n">c</span><span class="p">[</span><span class="n">i</span><span class="p">],</span><span class="n">d</span><span class="p">[</span><span class="n">i</span><span class="p">],</span><span class="mi">1</span><span class="p">,</span><span class="n">i</span><span class="p">));</span>
<span class="linenos" data-linenos="141 "></span>        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
<span class="linenos" data-linenos="142 "></span>            <span class="k">static</span> <span class="kt">int</span> <span class="n">tmp</span><span class="p">[</span><span class="n">L</span><span class="p">],</span><span class="n">C</span><span class="p">[</span><span class="n">L</span><span class="p">],</span><span class="n">D</span><span class="p">[</span><span class="n">L</span><span class="p">];</span>
<span class="linenos" data-linenos="143 "></span>            <span class="n">pre</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">],</span><span class="n">tmp</span><span class="p">);</span><span class="n">T1</span><span class="o">::</span><span class="n">insert</span><span class="p">(</span><span class="n">tmp</span><span class="p">);</span>
<span class="linenos" data-linenos="144 "></span>            <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">j</span><span class="o">&lt;</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">size</span><span class="p">();</span><span class="n">j</span><span class="o">++</span><span class="p">){</span>
<span class="linenos" data-linenos="145 "></span>                <span class="n">pre</span><span class="p">(</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">].</span><span class="n">c</span><span class="p">,</span><span class="n">C</span><span class="p">);</span>
<span class="linenos" data-linenos="146 "></span>                <span class="n">pre</span><span class="p">(</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">].</span><span class="n">d</span><span class="p">,</span><span class="n">D</span><span class="p">);</span>
<span class="linenos" data-linenos="147 "></span>                <span class="n">ans</span><span class="p">[</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">].</span><span class="n">id</span><span class="p">]</span><span class="o">+=</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">].</span><span class="n">op</span><span class="o">*</span><span class="n">T1</span><span class="o">::</span><span class="n">qry</span><span class="p">(</span><span class="n">C</span><span class="p">,</span><span class="n">D</span><span class="p">);</span>
<span class="linenos" data-linenos="148 "></span>            <span class="p">}</span>
<span class="linenos" data-linenos="149 "></span>        <span class="p">}</span>
<span class="linenos" data-linenos="150 "></span>    <span class="p">}</span>
<span class="linenos" data-linenos="151 "></span><span class="p">}</span>
<span class="linenos" data-linenos="152 "></span><span class="k">namespace</span> <span class="n">solve3</span><span class="p">{</span>
<span class="linenos" data-linenos="153 "></span>    <span class="c1">//min d&gt;=max b 的情况，限制的因素是b </span>
<span class="linenos" data-linenos="154 "></span>    <span class="c1">//首先差分，然后建01-tire</span>
<span class="linenos" data-linenos="155 "></span>    <span class="k">struct</span> <span class="nc">node</span><span class="p">{</span><span class="kt">int</span> <span class="n">c</span><span class="p">,</span><span class="n">op</span><span class="p">,</span><span class="n">id</span><span class="p">;</span><span class="n">node</span><span class="p">(</span><span class="kt">int</span> <span class="n">_</span><span class="p">,</span><span class="kt">int</span> <span class="n">__</span><span class="p">,</span><span class="kt">int</span> <span class="n">___</span><span class="p">)</span><span class="o">:</span><span class="n">c</span><span class="p">(</span><span class="n">_</span><span class="p">),</span><span class="n">op</span><span class="p">(</span><span class="n">__</span><span class="p">),</span><span class="n">id</span><span class="p">(</span><span class="n">___</span><span class="p">){}};</span>
<span class="linenos" data-linenos="156 "></span>    <span class="n">std</span><span class="o">::</span><span class="n">vector</span><span class="o">&lt;</span><span class="n">node</span><span class="o">&gt;</span><span class="n">Q</span><span class="p">[</span><span class="n">N</span><span class="p">];</span>
<span class="linenos" data-linenos="157 "></span>    <span class="kt">void</span> <span class="nf">work</span><span class="p">(){</span>
<span class="linenos" data-linenos="158 "></span>        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">q</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span>
<span class="linenos" data-linenos="159 "></span>            <span class="n">Q</span><span class="p">[</span><span class="n">l</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="mi">-1</span><span class="p">].</span><span class="n">push_back</span><span class="p">(</span><span class="n">node</span><span class="p">(</span><span class="n">c</span><span class="p">[</span><span class="n">i</span><span class="p">],</span><span class="mi">-1</span><span class="p">,</span><span class="n">i</span><span class="p">)),</span>
<span class="linenos" data-linenos="160 "></span>            <span class="n">Q</span><span class="p">[</span><span class="n">r</span><span class="p">[</span><span class="n">i</span><span class="p">]].</span><span class="n">push_back</span><span class="p">(</span><span class="n">node</span><span class="p">(</span><span class="n">c</span><span class="p">[</span><span class="n">i</span><span class="p">],</span><span class="mi">1</span><span class="p">,</span><span class="n">i</span><span class="p">));</span>
<span class="linenos" data-linenos="161 "></span>        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
<span class="linenos" data-linenos="162 "></span>            <span class="k">static</span> <span class="kt">int</span> <span class="n">A</span><span class="p">[</span><span class="n">L</span><span class="p">],</span><span class="n">B</span><span class="p">[</span><span class="n">L</span><span class="p">],</span><span class="n">C</span><span class="p">[</span><span class="n">L</span><span class="p">];</span>
<span class="linenos" data-linenos="163 "></span>            <span class="n">pre</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">],</span><span class="n">A</span><span class="p">);</span><span class="n">pre</span><span class="p">(</span><span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">],</span><span class="n">B</span><span class="p">);</span><span class="n">T2</span><span class="o">::</span><span class="n">insert</span><span class="p">(</span><span class="n">A</span><span class="p">,</span><span class="n">B</span><span class="p">);</span>
<span class="linenos" data-linenos="164 "></span>            <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">j</span><span class="o">&lt;</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">size</span><span class="p">();</span><span class="n">j</span><span class="o">++</span><span class="p">){</span>
<span class="linenos" data-linenos="165 "></span>                <span class="n">pre</span><span class="p">(</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">].</span><span class="n">c</span><span class="p">,</span><span class="n">C</span><span class="p">);</span>
<span class="linenos" data-linenos="166 "></span>                <span class="n">ans</span><span class="p">[</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">].</span><span class="n">id</span><span class="p">]</span><span class="o">+=</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">].</span><span class="n">op</span><span class="o">*</span><span class="n">T2</span><span class="o">::</span><span class="n">qry</span><span class="p">(</span><span class="n">C</span><span class="p">);</span>
<span class="linenos" data-linenos="167 "></span>            <span class="p">}</span>
<span class="linenos" data-linenos="168 "></span>        <span class="p">}</span>
<span class="linenos" data-linenos="169 "></span>    <span class="p">}</span>
<span class="linenos" data-linenos="170 "></span><span class="p">}</span>
<span class="linenos" data-linenos="171 "></span><span class="k">namespace</span> <span class="n">solve4</span><span class="p">{</span>
<span class="linenos" data-linenos="172 "></span>    <span class="k">struct</span> <span class="nc">node</span><span class="p">{</span>
<span class="linenos" data-linenos="173 "></span>        <span class="kt">int</span> <span class="n">id</span><span class="p">,</span><span class="n">c</span><span class="p">,</span><span class="n">d</span><span class="p">;</span>
<span class="linenos" data-linenos="174 "></span>        <span class="kt">bool</span> <span class="k">operator</span><span class="o">&lt;</span><span class="p">(</span><span class="k">const</span> <span class="n">node</span> <span class="n">b</span><span class="p">)</span><span class="k">const</span><span class="p">{</span><span class="k">return</span> <span class="n">d</span><span class="o">&lt;</span><span class="n">b</span><span class="p">.</span><span class="n">d</span><span class="p">;}</span>
<span class="linenos" data-linenos="175 "></span>    <span class="p">}</span><span class="n">Q</span><span class="p">[</span><span class="n">N</span><span class="p">];</span>
<span class="linenos" data-linenos="176 "></span>    <span class="n">std</span><span class="o">::</span><span class="n">pair</span><span class="o">&lt;</span><span class="kt">int</span><span class="p">,</span><span class="kt">int</span><span class="o">&gt;</span><span class="n">kk</span><span class="p">[</span><span class="n">N</span><span class="p">];</span>
<span class="linenos" data-linenos="177 "></span>    <span class="kt">void</span> <span class="nf">work</span><span class="p">(){</span>
<span class="linenos" data-linenos="178 "></span>        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">q</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span>
<span class="linenos" data-linenos="179 "></span>            <span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">id</span><span class="o">=</span><span class="n">i</span><span class="p">,</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">c</span><span class="o">=</span><span class="n">c</span><span class="p">[</span><span class="n">i</span><span class="p">],</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">d</span><span class="o">=</span><span class="n">d</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
<span class="linenos" data-linenos="180 "></span>        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span><span class="n">kk</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">first</span><span class="o">=</span><span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">],</span><span class="n">kk</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">second</span><span class="o">=</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
<span class="linenos" data-linenos="181 "></span>        <span class="n">std</span><span class="o">::</span><span class="n">sort</span><span class="p">(</span><span class="n">Q</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span><span class="n">Q</span><span class="o">+</span><span class="mi">1</span><span class="o">+</span><span class="n">q</span><span class="p">);</span><span class="n">std</span><span class="o">::</span><span class="n">sort</span><span class="p">(</span><span class="n">kk</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span><span class="n">kk</span><span class="o">+</span><span class="mi">1</span><span class="o">+</span><span class="n">n</span><span class="p">);</span>
<span class="linenos" data-linenos="182 "></span>        <span class="kt">int</span> <span class="n">now</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
<span class="linenos" data-linenos="183 "></span>        <span class="k">static</span> <span class="kt">int</span> <span class="n">A</span><span class="p">[</span><span class="n">L</span><span class="p">],</span><span class="n">B</span><span class="p">[</span><span class="n">L</span><span class="p">],</span><span class="n">C</span><span class="p">[</span><span class="n">L</span><span class="p">],</span><span class="n">D</span><span class="p">[</span><span class="n">L</span><span class="p">];</span>
<span class="linenos" data-linenos="184 "></span>        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">q</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
<span class="linenos" data-linenos="185 "></span>            <span class="k">while</span><span class="p">(</span><span class="n">now</span><span class="o">+</span><span class="mi">1</span><span class="o">&lt;=</span><span class="n">n</span><span class="o">&amp;&amp;</span><span class="n">kk</span><span class="p">[</span><span class="n">now</span><span class="o">+</span><span class="mi">1</span><span class="p">].</span><span class="n">first</span><span class="o">&lt;=</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">d</span><span class="p">){</span>
<span class="linenos" data-linenos="186 "></span>                <span class="n">now</span><span class="o">++</span><span class="p">;</span>
<span class="linenos" data-linenos="187 "></span>                <span class="n">pre</span><span class="p">(</span><span class="n">kk</span><span class="p">[</span><span class="n">now</span><span class="p">].</span><span class="n">first</span><span class="p">,</span><span class="n">B</span><span class="p">);</span>
<span class="linenos" data-linenos="188 "></span>                <span class="n">pre</span><span class="p">(</span><span class="n">kk</span><span class="p">[</span><span class="n">now</span><span class="p">].</span><span class="n">second</span><span class="p">,</span><span class="n">A</span><span class="p">);</span>
<span class="linenos" data-linenos="189 "></span>                <span class="n">T2</span><span class="o">::</span><span class="n">insert</span><span class="p">(</span><span class="n">A</span><span class="p">,</span><span class="n">B</span><span class="p">);</span>
<span class="linenos" data-linenos="190 "></span>            <span class="p">}</span>
<span class="linenos" data-linenos="191 "></span>            <span class="n">pre</span><span class="p">(</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">c</span><span class="p">,</span><span class="n">C</span><span class="p">);</span>
<span class="linenos" data-linenos="192 "></span>            <span class="n">ans</span><span class="p">[</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">id</span><span class="p">]</span><span class="o">+=</span><span class="n">T2</span><span class="o">::</span><span class="n">qry</span><span class="p">(</span><span class="n">C</span><span class="p">);</span>
<span class="linenos" data-linenos="193 "></span>        <span class="p">}</span>
<span class="linenos" data-linenos="194 "></span>        <span class="n">now</span><span class="o">=</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">;</span>
<span class="linenos" data-linenos="195 "></span>        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="n">q</span><span class="p">;</span><span class="n">i</span><span class="o">&gt;=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">--</span><span class="p">){</span>
<span class="linenos" data-linenos="196 "></span>            <span class="k">while</span><span class="p">(</span><span class="n">now</span><span class="o">&gt;</span><span class="mi">1</span><span class="o">&amp;&amp;</span><span class="n">kk</span><span class="p">[</span><span class="n">now</span><span class="mi">-1</span><span class="p">].</span><span class="n">first</span><span class="o">&gt;</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">d</span><span class="p">){</span>
<span class="linenos" data-linenos="197 "></span>                <span class="n">now</span><span class="o">--</span><span class="p">;</span>
<span class="linenos" data-linenos="198 "></span>                <span class="n">pre</span><span class="p">(</span><span class="n">kk</span><span class="p">[</span><span class="n">now</span><span class="p">].</span><span class="n">second</span><span class="p">,</span><span class="n">A</span><span class="p">);</span>
<span class="linenos" data-linenos="199 "></span>                <span class="n">T1</span><span class="o">::</span><span class="n">insert</span><span class="p">(</span><span class="n">A</span><span class="p">);</span>
<span class="linenos" data-linenos="200 "></span>            <span class="p">}</span>
<span class="linenos" data-linenos="201 "></span>            <span class="n">pre</span><span class="p">(</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">c</span><span class="p">,</span><span class="n">C</span><span class="p">);</span>
<span class="linenos" data-linenos="202 "></span>            <span class="n">pre</span><span class="p">(</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">d</span><span class="p">,</span><span class="n">D</span><span class="p">);</span>
<span class="linenos" data-linenos="203 "></span>            <span class="n">ans</span><span class="p">[</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">id</span><span class="p">]</span><span class="o">+=</span><span class="n">T1</span><span class="o">::</span><span class="n">qry</span><span class="p">(</span><span class="n">C</span><span class="p">,</span><span class="n">D</span><span class="p">);</span>
<span class="linenos" data-linenos="204 "></span>        <span class="p">}</span>
<span class="linenos" data-linenos="205 "></span>    <span class="p">}</span>
<span class="linenos" data-linenos="206 "></span><span class="p">}</span>
<span class="linenos" data-linenos="207 "></span><span class="k">namespace</span> <span class="n">solve5</span><span class="p">{</span>
<span class="linenos" data-linenos="208 "></span>    <span class="k">struct</span> <span class="nc">node</span><span class="p">{</span>
<span class="linenos" data-linenos="209 "></span>        <span class="kt">int</span> <span class="n">id</span><span class="p">,</span><span class="n">l</span><span class="p">,</span><span class="n">r</span><span class="p">,</span><span class="n">c</span><span class="p">,</span><span class="n">d</span><span class="p">;</span>
<span class="linenos" data-linenos="210 "></span>        <span class="kt">bool</span> <span class="k">operator</span><span class="o">&lt;</span><span class="p">(</span><span class="k">const</span> <span class="n">node</span> <span class="n">b</span><span class="p">)</span><span class="k">const</span><span class="p">{</span><span class="k">return</span> <span class="n">d</span><span class="o">&lt;</span><span class="n">b</span><span class="p">.</span><span class="n">d</span><span class="p">;}</span>
<span class="linenos" data-linenos="211 "></span>    <span class="p">}</span><span class="n">Q</span><span class="p">[</span><span class="n">N</span><span class="p">];</span>
<span class="linenos" data-linenos="212 "></span>    <span class="n">std</span><span class="o">::</span><span class="n">pair</span><span class="o">&lt;</span><span class="kt">int</span><span class="p">,</span><span class="kt">int</span><span class="o">&gt;</span><span class="n">kk</span><span class="p">[</span><span class="n">N</span><span class="p">];</span>
<span class="linenos" data-linenos="213 "></span>    <span class="kt">void</span> <span class="nf">work</span><span class="p">(){</span>
<span class="linenos" data-linenos="214 "></span>        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">q</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span>
<span class="linenos" data-linenos="215 "></span>            <span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">id</span><span class="o">=</span><span class="n">i</span><span class="p">,</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">c</span><span class="o">=</span><span class="n">c</span><span class="p">[</span><span class="n">i</span><span class="p">],</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">d</span><span class="o">=</span><span class="n">d</span><span class="p">[</span><span class="n">i</span><span class="p">],</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">l</span><span class="o">=</span><span class="n">l</span><span class="p">[</span><span class="n">i</span><span class="p">],</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">r</span><span class="o">=</span><span class="n">r</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
<span class="linenos" data-linenos="216 "></span>        <span class="n">std</span><span class="o">::</span><span class="n">sort</span><span class="p">(</span><span class="n">Q</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span><span class="n">Q</span><span class="o">+</span><span class="mi">1</span><span class="o">+</span><span class="n">q</span><span class="p">);</span>
<span class="linenos" data-linenos="217 "></span>        <span class="kt">int</span> <span class="n">sz</span><span class="o">=</span><span class="mi">1800</span><span class="p">;</span>
<span class="linenos" data-linenos="218 "></span>        <span class="k">static</span> <span class="kt">int</span> <span class="n">A</span><span class="p">[</span><span class="n">L</span><span class="p">],</span><span class="n">B</span><span class="p">[</span><span class="n">L</span><span class="p">],</span><span class="n">C</span><span class="p">[</span><span class="n">L</span><span class="p">],</span><span class="n">D</span><span class="p">[</span><span class="n">L</span><span class="p">];</span>
<span class="linenos" data-linenos="219 "></span>        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">l</span><span class="o">=</span><span class="mi">1</span><span class="p">,</span><span class="n">r</span><span class="p">;</span><span class="n">l</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span><span class="n">l</span><span class="o">=</span><span class="n">r</span><span class="o">+</span><span class="mi">1</span><span class="p">){</span>
<span class="linenos" data-linenos="220 "></span>            <span class="n">r</span><span class="o">=</span><span class="n">min</span><span class="p">(</span><span class="n">l</span><span class="o">+</span><span class="n">sz</span><span class="p">,</span><span class="n">n</span><span class="p">);</span><span class="kt">int</span> <span class="n">len</span><span class="o">=</span><span class="n">r</span><span class="o">-</span><span class="n">l</span><span class="o">+</span><span class="mi">1</span><span class="p">;</span>
<span class="linenos" data-linenos="221 "></span>            <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="n">l</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">r</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span><span class="n">kk</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="n">l</span><span class="o">+</span><span class="mi">1</span><span class="p">].</span><span class="n">first</span><span class="o">=</span><span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">],</span><span class="n">kk</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="n">l</span><span class="o">+</span><span class="mi">1</span><span class="p">].</span><span class="n">second</span><span class="o">=</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
<span class="linenos" data-linenos="222 "></span>            <span class="n">sort</span><span class="p">(</span><span class="n">kk</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span><span class="n">kk</span><span class="o">+</span><span class="mi">1</span><span class="o">+</span><span class="n">len</span><span class="p">);</span>
<span class="linenos" data-linenos="223 "></span>            <span class="kt">int</span> <span class="n">now</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
<span class="linenos" data-linenos="224 "></span>            <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">q</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
<span class="linenos" data-linenos="225 "></span>                <span class="kt">int</span> <span class="n">ll</span><span class="o">=</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">l</span><span class="p">,</span><span class="n">rr</span><span class="o">=</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">r</span><span class="p">;</span>
<span class="linenos" data-linenos="226 "></span>                <span class="k">if</span><span class="p">(</span><span class="n">ll</span><span class="o">&gt;</span><span class="n">l</span><span class="o">||</span><span class="n">r</span><span class="o">&gt;</span><span class="n">rr</span><span class="p">)</span><span class="k">continue</span><span class="p">;</span>
<span class="linenos" data-linenos="227 "></span>                <span class="k">while</span><span class="p">(</span><span class="n">now</span><span class="o">+</span><span class="mi">1</span><span class="o">&lt;=</span><span class="n">len</span><span class="o">&amp;&amp;</span><span class="n">kk</span><span class="p">[</span><span class="n">now</span><span class="o">+</span><span class="mi">1</span><span class="p">].</span><span class="n">first</span><span class="o">&lt;=</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">d</span><span class="p">){</span>
<span class="linenos" data-linenos="228 "></span>                    <span class="n">now</span><span class="o">++</span><span class="p">;</span>
<span class="linenos" data-linenos="229 "></span>                    <span class="n">pre</span><span class="p">(</span><span class="n">kk</span><span class="p">[</span><span class="n">now</span><span class="p">].</span><span class="n">first</span><span class="p">,</span><span class="n">B</span><span class="p">);</span>
<span class="linenos" data-linenos="230 "></span>                    <span class="n">pre</span><span class="p">(</span><span class="n">kk</span><span class="p">[</span><span class="n">now</span><span class="p">].</span><span class="n">second</span><span class="p">,</span><span class="n">A</span><span class="p">);</span>
<span class="linenos" data-linenos="231 "></span>                    <span class="n">T2</span><span class="o">::</span><span class="n">insert</span><span class="p">(</span><span class="n">A</span><span class="p">,</span><span class="n">B</span><span class="p">);</span>
<span class="linenos" data-linenos="232 "></span>                <span class="p">}</span>
<span class="linenos" data-linenos="233 "></span>                <span class="n">pre</span><span class="p">(</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">c</span><span class="p">,</span><span class="n">C</span><span class="p">);</span>
<span class="linenos" data-linenos="234 "></span>                <span class="n">ans</span><span class="p">[</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">id</span><span class="p">]</span><span class="o">+=</span><span class="n">T2</span><span class="o">::</span><span class="n">qry</span><span class="p">(</span><span class="n">C</span><span class="p">);</span>
<span class="linenos" data-linenos="235 "></span>            <span class="p">}</span>
<span class="linenos" data-linenos="236 "></span>            <span class="n">now</span><span class="o">=</span><span class="n">len</span><span class="o">+</span><span class="mi">1</span><span class="p">;</span>
<span class="linenos" data-linenos="237 "></span>            <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="n">q</span><span class="p">;</span><span class="n">i</span><span class="o">&gt;=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">--</span><span class="p">){</span>
<span class="linenos" data-linenos="238 "></span>                <span class="kt">int</span> <span class="n">ll</span><span class="o">=</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">l</span><span class="p">,</span><span class="n">rr</span><span class="o">=</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">r</span><span class="p">;</span>
<span class="linenos" data-linenos="239 "></span>                <span class="k">if</span><span class="p">(</span><span class="n">ll</span><span class="o">&gt;</span><span class="n">l</span><span class="o">||</span><span class="n">r</span><span class="o">&gt;</span><span class="n">rr</span><span class="p">)</span><span class="k">continue</span><span class="p">;</span>
<span class="linenos" data-linenos="240 "></span>                <span class="k">while</span><span class="p">(</span><span class="n">now</span><span class="o">&gt;</span><span class="mi">1</span><span class="o">&amp;&amp;</span><span class="n">kk</span><span class="p">[</span><span class="n">now</span><span class="mi">-1</span><span class="p">].</span><span class="n">first</span><span class="o">&gt;</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">d</span><span class="p">){</span>
<span class="linenos" data-linenos="241 "></span>                    <span class="n">now</span><span class="o">--</span><span class="p">;</span>
<span class="linenos" data-linenos="242 "></span>                    <span class="n">pre</span><span class="p">(</span><span class="n">kk</span><span class="p">[</span><span class="n">now</span><span class="p">].</span><span class="n">second</span><span class="p">,</span><span class="n">A</span><span class="p">);</span>
<span class="linenos" data-linenos="243 "></span>                    <span class="n">T1</span><span class="o">::</span><span class="n">insert</span><span class="p">(</span><span class="n">A</span><span class="p">);</span>
<span class="linenos" data-linenos="244 "></span>                <span class="p">}</span>
<span class="linenos" data-linenos="245 "></span>                <span class="n">pre</span><span class="p">(</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">c</span><span class="p">,</span><span class="n">C</span><span class="p">);</span>
<span class="linenos" data-linenos="246 "></span>                <span class="n">pre</span><span class="p">(</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">d</span><span class="p">,</span><span class="n">D</span><span class="p">);</span>
<span class="linenos" data-linenos="247 "></span>                <span class="n">ans</span><span class="p">[</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">id</span><span class="p">]</span><span class="o">+=</span><span class="n">T1</span><span class="o">::</span><span class="n">qry</span><span class="p">(</span><span class="n">C</span><span class="p">,</span><span class="n">D</span><span class="p">);</span>
<span class="linenos" data-linenos="248 "></span>            <span class="p">}</span>
<span class="linenos" data-linenos="249 "></span>            <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">q</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
<span class="linenos" data-linenos="250 "></span>                <span class="kt">int</span> <span class="n">ll</span><span class="o">=</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">l</span><span class="p">,</span><span class="n">rr</span><span class="o">=</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">r</span><span class="p">;</span>
<span class="linenos" data-linenos="251 "></span>                <span class="k">if</span><span class="p">(</span><span class="n">ll</span><span class="o">&lt;=</span><span class="n">l</span><span class="o">&amp;&amp;</span><span class="n">r</span><span class="o">&lt;=</span><span class="n">rr</span><span class="p">)</span><span class="k">continue</span><span class="p">;</span>
<span class="linenos" data-linenos="252 "></span>                <span class="n">ll</span><span class="o">=</span><span class="n">max</span><span class="p">(</span><span class="n">ll</span><span class="p">,</span><span class="n">l</span><span class="p">);</span><span class="n">rr</span><span class="o">=</span><span class="n">min</span><span class="p">(</span><span class="n">rr</span><span class="p">,</span><span class="n">r</span><span class="p">);</span>
<span class="linenos" data-linenos="253 "></span>                <span class="kt">unsigned</span> <span class="kt">short</span> <span class="n">sum1</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span><span class="n">sum2</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span><span class="n">sum3</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span><span class="n">sum4</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span><span class="n">sum5</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span><span class="n">sum6</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
<span class="linenos" data-linenos="254 "></span>                <span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="n">ll</span><span class="p">;</span>
<span class="linenos" data-linenos="255 "></span>                <span class="k">for</span><span class="p">(;</span><span class="n">j</span><span class="o">+</span><span class="mi">5</span><span class="o">&lt;=</span><span class="n">rr</span><span class="p">;</span><span class="n">j</span><span class="o">+=</span><span class="mi">6</span><span class="p">)</span>
<span class="linenos" data-linenos="256 "></span>                    <span class="n">sum1</span><span class="o">+=</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">j</span>  <span class="p">]</span><span class="o">^</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">c</span><span class="p">)</span><span class="o">&lt;=</span><span class="n">min</span><span class="p">(</span><span class="n">b</span><span class="p">[</span><span class="n">j</span>  <span class="p">],</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">d</span><span class="p">),</span>
<span class="linenos" data-linenos="257 "></span>                    <span class="n">sum2</span><span class="o">+=</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">j</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span><span class="o">^</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">c</span><span class="p">)</span><span class="o">&lt;=</span><span class="n">min</span><span class="p">(</span><span class="n">b</span><span class="p">[</span><span class="n">j</span><span class="o">+</span><span class="mi">1</span><span class="p">],</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">d</span><span class="p">),</span>
<span class="linenos" data-linenos="258 "></span>                    <span class="n">sum3</span><span class="o">+=</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">j</span><span class="o">+</span><span class="mi">2</span><span class="p">]</span><span class="o">^</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">c</span><span class="p">)</span><span class="o">&lt;=</span><span class="n">min</span><span class="p">(</span><span class="n">b</span><span class="p">[</span><span class="n">j</span><span class="o">+</span><span class="mi">2</span><span class="p">],</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">d</span><span class="p">),</span>
<span class="linenos" data-linenos="259 "></span>                    <span class="n">sum4</span><span class="o">+=</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">j</span><span class="o">+</span><span class="mi">3</span><span class="p">]</span><span class="o">^</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">c</span><span class="p">)</span><span class="o">&lt;=</span><span class="n">min</span><span class="p">(</span><span class="n">b</span><span class="p">[</span><span class="n">j</span><span class="o">+</span><span class="mi">3</span><span class="p">],</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">d</span><span class="p">),</span>
<span class="linenos" data-linenos="260 "></span>                    <span class="n">sum5</span><span class="o">+=</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">j</span><span class="o">+</span><span class="mi">4</span><span class="p">]</span><span class="o">^</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">c</span><span class="p">)</span><span class="o">&lt;=</span><span class="n">min</span><span class="p">(</span><span class="n">b</span><span class="p">[</span><span class="n">j</span><span class="o">+</span><span class="mi">4</span><span class="p">],</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">d</span><span class="p">),</span>
<span class="linenos" data-linenos="261 "></span>                    <span class="n">sum6</span><span class="o">+=</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">j</span><span class="o">+</span><span class="mi">5</span><span class="p">]</span><span class="o">^</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">c</span><span class="p">)</span><span class="o">&lt;=</span><span class="n">min</span><span class="p">(</span><span class="n">b</span><span class="p">[</span><span class="n">j</span><span class="o">+</span><span class="mi">5</span><span class="p">],</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">d</span><span class="p">);</span>
<span class="linenos" data-linenos="262 "></span>                <span class="k">for</span><span class="p">(;</span><span class="n">j</span><span class="o">&lt;=</span><span class="n">rr</span><span class="p">;</span><span class="n">j</span><span class="o">++</span><span class="p">)</span>
<span class="linenos" data-linenos="263 "></span>                    <span class="n">sum1</span><span class="o">+=</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">j</span>  <span class="p">]</span><span class="o">^</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">c</span><span class="p">)</span><span class="o">&lt;=</span><span class="n">min</span><span class="p">(</span><span class="n">b</span><span class="p">[</span><span class="n">j</span>  <span class="p">],</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">d</span><span class="p">);</span>
<span class="linenos" data-linenos="264 "></span>                <span class="n">ans</span><span class="p">[</span><span class="n">Q</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">id</span><span class="p">]</span><span class="o">+=</span><span class="n">sum1</span><span class="o">+</span><span class="n">sum2</span><span class="o">+</span><span class="n">sum3</span><span class="o">+</span><span class="n">sum4</span><span class="o">+</span><span class="n">sum5</span><span class="o">+</span><span class="n">sum6</span><span class="p">;</span>
<span class="linenos" data-linenos="265 "></span>            <span class="p">}</span>
<span class="linenos" data-linenos="266 "></span>            <span class="n">T1</span><span class="o">::</span><span class="n">clear</span><span class="p">();</span>
<span class="linenos" data-linenos="267 "></span>            <span class="n">T2</span><span class="o">::</span><span class="n">clear</span><span class="p">();</span>
<span class="linenos" data-linenos="268 "></span>        <span class="p">}</span>
<span class="linenos" data-linenos="269 "></span>    <span class="p">}</span>
<span class="linenos" data-linenos="270 "></span><span class="p">}</span>
<span class="linenos" data-linenos="271 "></span><span class="kt">signed</span> <span class="n">main</span><span class="p">(){</span>
<span class="linenos" data-linenos="272 "></span>    <span class="c1">//freopen(&quot;island.in&quot;,&quot;r&quot;,stdin);</span>
<span class="linenos" data-linenos="273 "></span>    <span class="c1">//freopen(&quot;island.out&quot;,&quot;w&quot;,stdout);</span>
<span class="linenos" data-linenos="274 "></span>    <span class="n">in</span><span class="o">::</span><span class="n">read</span><span class="p">(</span><span class="n">n</span><span class="p">,</span><span class="n">q</span><span class="p">);</span>
<span class="linenos" data-linenos="275 "></span>    <span class="kt">int</span> <span class="n">mnb</span><span class="o">=</span><span class="mh">0x3f3f3f3f</span><span class="p">,</span><span class="n">mxb</span><span class="o">=</span><span class="mh">-0x3f3f3f3f</span><span class="p">;</span>
<span class="linenos" data-linenos="276 "></span>    <span class="kt">int</span> <span class="n">mnd</span><span class="o">=</span><span class="mh">0x3f3f3f3f</span><span class="p">,</span><span class="n">mxd</span><span class="o">=</span><span class="mh">-0x3f3f3f3f</span><span class="p">;</span>
<span class="linenos" data-linenos="277 "></span>    <span class="kt">bool</span> <span class="n">flag</span><span class="o">=</span><span class="nb">true</span><span class="p">;</span>
<span class="linenos" data-linenos="278 "></span>    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span><span class="n">in</span><span class="o">::</span><span class="n">read</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">],</span><span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">]),</span><span class="n">mnb</span><span class="o">=</span><span class="n">min</span><span class="p">(</span><span class="n">mnb</span><span class="p">,</span><span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">]),</span><span class="n">mxb</span><span class="o">=</span><span class="n">max</span><span class="p">(</span><span class="n">mxb</span><span class="p">,</span><span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span>
<span class="linenos" data-linenos="279 "></span>    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">q</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span><span class="n">in</span><span class="o">::</span><span class="n">read</span><span class="p">(</span><span class="n">l</span><span class="p">[</span><span class="n">i</span><span class="p">],</span><span class="n">r</span><span class="p">[</span><span class="n">i</span><span class="p">],</span><span class="n">c</span><span class="p">[</span><span class="n">i</span><span class="p">],</span><span class="n">d</span><span class="p">[</span><span class="n">i</span><span class="p">]),</span><span class="n">mnd</span><span class="o">=</span><span class="n">min</span><span class="p">(</span><span class="n">mnd</span><span class="p">,</span><span class="n">d</span><span class="p">[</span><span class="n">i</span><span class="p">]),</span><span class="n">mxd</span><span class="o">=</span><span class="n">max</span><span class="p">(</span><span class="n">mxd</span><span class="p">,</span><span class="n">d</span><span class="p">[</span><span class="n">i</span><span class="p">]),</span><span class="n">flag</span><span class="o">&amp;=</span><span class="p">(</span><span class="n">l</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">==</span><span class="mi">1</span><span class="o">&amp;&amp;</span><span class="n">r</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">==</span><span class="n">n</span><span class="p">);</span>
<span class="linenos" data-linenos="280 "></span>    <span class="k">if</span><span class="p">(</span><span class="n">n</span><span class="o">&lt;=</span><span class="mi">5000</span><span class="p">)</span><span class="n">solve1</span><span class="o">::</span><span class="n">work</span><span class="p">();</span>
<span class="linenos" data-linenos="281 "></span>    <span class="k">else</span> <span class="nf">if</span><span class="p">(</span><span class="n">mxd</span><span class="o">&lt;=</span><span class="n">mnb</span><span class="p">)</span><span class="n">solve2</span><span class="o">::</span><span class="n">work</span><span class="p">();</span>
<span class="linenos" data-linenos="282 "></span>    <span class="k">else</span> <span class="nf">if</span><span class="p">(</span><span class="n">mnd</span><span class="o">&gt;=</span><span class="n">mxb</span><span class="p">)</span><span class="n">solve3</span><span class="o">::</span><span class="n">work</span><span class="p">();</span>
<span class="linenos" data-linenos="283 "></span>    <span class="k">else</span> <span class="nf">if</span><span class="p">(</span><span class="n">flag</span><span class="p">)</span><span class="n">solve4</span><span class="o">::</span><span class="n">work</span><span class="p">();</span>
<span class="linenos" data-linenos="284 "></span>    <span class="k">else</span> <span class="n">solve5</span><span class="o">::</span><span class="n">work</span><span class="p">();</span>
<span class="linenos" data-linenos="285 "></span>    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">q</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span><span class="n">out</span><span class="o">::</span><span class="n">write</span><span class="p">(</span><span class="n">ans</span><span class="p">[</span><span class="n">i</span><span class="p">]),</span><span class="n">out</span><span class="o">::</span><span class="n">putc</span><span class="p">(</span><span class="sc">&#39;\n&#39;</span><span class="p">);</span>
<span class="linenos" data-linenos="286 "></span>    <span class="n">out</span><span class="o">::</span><span class="n">flush</span><span class="p">();</span>
<span class="linenos" data-linenos="287 "></span>    <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
<span class="linenos" data-linenos="288 "></span><span class="p">}</span>
</code></pre></div>
			</div>
			<div class="panel panel-default card" style="padding: 10px;height: 50px;font-size: 20px;">
				<a style="float: left;" href="\article\P4500.html"><i class="fa fa-angle-double-left"></i></a><a style="float: right;" href="\article\AnalComb.html"><i class="fa fa-angle-double-right"></i></a>
			</div>
			<div class="panel panel-default card" style="padding: 10px;font-size: 20px;" id="vcomments">
				
			</div>
			<script>
				new Valine({
					el: '#vcomments',
					appId: 'PAlFUPg0pQVTFTEo8gCB4BCf-gzGzoHsz',
					appKey: 'U38ejnLUiizJ6vLyp6ql4hRq',
					path: window.location.pathname
				})
			</script>
		</div>
		<div class="col-md-3">
				<div class="panel panel-default card">
				<div class="panel-heading">
					<h3 class="panel-title">
						<i class="fa fa-info"></i>&emsp;
						<strong>文章信息</strong>
					</h3>
				</div>
                <div style="margin: 10px;">
                    <div style="margin-top: 8px;display: flex;"> 
    <span style="flex: 1 0 auto;margin-right: 6px;">标题</span>
    <span><font style="font-weight: bold">题解 P7470 【[NOI Online 2021 提高组] 岛屿探险】</font></span>
	</div><div style="margin-top: 8px;display: flex;"> 
    <span style="flex: 1 0 auto;margin-right: 6px;">日期</span>
    <span>2021-03-28 21:08:21</span>
	</div>
                </div>
				</div>
				<div class="panel panel-default card">
				<div class="panel-heading">
					<h3 class="panel-title">
						<i class="fa fa-tag"></i>&emsp;
						<strong>标签</strong>
					</h3>
				</div>
				<div style="margin: 10px;">
					<a href="/tags/2021/" class="tag"><span  style="background-color: rgb(52, 152, 219);">2021</span></a>&nbsp;<a href="/tags/tire/" class="tag"><span  style="background-color: rgb(231, 76, 60);">tire</span></a>&nbsp;<a href="/tags/分块/" class="tag"><span  style="background-color: rgb(231, 76, 60);">分块</span></a>&nbsp;<a href="/tags/题解/" class="tag"><span  style="background-color: rgb(82, 196, 26);">题解</span></a>
				</div>
				</div>
				
			<div class="panel panel-default card">
					<div class="panel-heading">
						<h3 class="panel-title">
							<i class="fa fa-user-circle-o"></i>&emsp;
							<strong>caijicjl</strong>
						</h3>
					</div>
					<div style="width: 60%;display: inline-block;padding-top: 10px;">
						<ul class="propertyLinks" style="list-style-type: none;">
							<li>
								<img style="vertical-align:middle;position:relative;top:-2px" src="/img/rating-16x16.png">
								Rating:&nbsp;
								<span style="font-weight:bold;color: gray ">312</span>
							</li>
							<li>
								<img style="vertical-align:middle;position:relative;top:-2px" src="/img/star_blue_16.png">
								Contribution:&nbsp;
								<span style="color:gray;font-weight:bold;">0</span>
							</li>
						</ul>
						<ul class="nav-links">
							<li><a href="/settings/">Settings</a></li>
							<li><a href="/archives/">Blog</a></li>
							<li><a href="/teams">Teams</a></li>
							<li><a href="/submissions/dingdingsb">Submissions</a></li>
							<li><a href="/usertalk">Talks</a></li>
							<li><a href="/contests/with/dingdingsb">Contests</a></li>
						</ul>
					</div>
					<div style="display:inline-block;vertical-align: top;margin: 10px;text-align: center;">
						<div style="height:50px;width:50px"><img src="/img/avatar.png"/></div>
						<div><a href="https://www.luogu.com.cn/user/174304" style="font-weight:bold;color:gray">caijicjl</a></div>
					</div>
				</div>
		<div class="panel panel-default card">
				<div class="panel-heading">
					<h3 class="panel-title">
						<i class="fa fa-external-link"></i>&emsp;
						<strong>画中画</strong>
					</h3>
				</div>
				<div style="width:100%;margin:10px">
				<input type="text" id="url"/>
				<input value="创建" type="button" onclick="creat('kk')" /> 
				</div>
		</div>
		<script src="/js/hitokoto.js"></script>
							

				
				<span id="kk"></span>
				<div  id="myScrollspy" class="card" style="width: 100%;"  data-spy="affix">
					<script src="/js/make_toc.js"></script>
				</div>
		</div>
	</div>
 </div>
</body>
</html>
